package code.linkedlist;

public class LinkedListAlgo {
    // 单链表反转
    public static Node reverse(Node list){
        Node cuur = list;
        Node pre = null;
        while (cuur != null){
            Node next = cuur.next;
            cuur.next = pre;
            pre = cuur;
            cuur = next;
        }
        return pre;
    }

    //检测环
    public static boolean checkCircle(Node list) {
        if (list == null){
            return false;
        }

        Node fast = list.next;
        Node slow = list;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    // 有序链表合并 Leetcode 21
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public Node mergeTwoLists(Node l1, Node l2) {
        //利用哨兵结点简化实现难度 技巧三
        Node soldier = createNode(0);
        Node p = soldier;
        while (l1 != null && l2 != null){
            if (l1.data < l2.data){
                p.next = l1;
                l1 = l1.next;
            }else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 != null){
            p.next = l1;
        }
        if (l2 != null){
            p.next = l2;
        }
        return soldier.next;
    }

    // 删除倒数第K个结点
    /**
     * 基本思路：

     　　让链表从头开始走到尾，每移动一步，就让k值减一，当k 值走到结尾时，

     　　如果k 值大于0，说明链表根本没有倒数第k 个节点

     　　如果等于0，那么头节点就是倒数第k 个节点，此时应该返回 head.next

     　　如果小于0，则重新从头节点开始，每移动一步，k 值增加一，当k 等于0时，移动停止，移动到的节点就是要删除节点的上一个节点
     */
    public static Node deleteLastKth(Node list, int k) {
        if (list == null || k < 0){
            return list;
        }
        Node cuur = list;
        while (cuur != null){
            cuur = cuur.next;
            k--;
        }
        if (k == 0){
            return list.next;
        }
        if (k > 0){
            return null;
        }
        if (k < 0){
            cuur = list;
            while (++k != 0){
                cuur = cuur.next;
            }
            return cuur.next;
        }
        return null;
    }

    // 求中间结点
    public static Node findMiddleNode(Node list){
        if (list == null || list.next == null){
            return list;
        }
        Node fast = list;
        Node slow = list;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void printAll(Node list) {
        Node p = list;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

}
